<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列。
                    </div>
                    <div>
                        2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步。
                    </div>
                    <div>
                        对于第i件物品，设它的所占容量为v[i]，价值为w[i]，我们可以选择该物品也可以不选择该物品，
                        如果不选择该物品则dp[i][j]=dp[i-1][j]dp[i][j]=dp[i−1][j]，
                        如果选择该物品有两种情况：
                    </div>
                    <div>
                        3) 在当前位置上满足条件的情形：
                        <ul>
                            <li>在当前位置放一个皇后，若当前行是最后一行，记录一个解；</li>
                            <li>若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；</li>
                            <li>若当前行是最后一行，当前列不是最后一列，当前列设为下一列；</li>
                            <li>若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；</li>
                        </ul>
                        以上返回到第2步。
                    </div>
                    <div>
                        4) 在当前位置上不满足条件的情形：
                    </div>
                    <div>
                        若当前列不是最后一列，当前列设为下一列，返回到第2步；
                    </div>
                    <div>
                        若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                            #include &lt;stdio.h>
                            #include &lt;stdlib.h>
                            #include &lt;math.h>
                            #define QUEEN 8     //皇后的数目
                            #define INITIAL -10000 //棋盘的初始值
                             
                            int a[QUEEN];    //一维数组表示棋盘
                            //对棋盘进行初始化
                            void init()  {
                                int *p;
                                for (p = a; p &lt; a + QUEEN; ++p) *p = INITIAL;
                            }
                             
                            //判断第row行第col列是否可以放置皇后
                            int valid(int row, int col){
                                int i;
                                //对棋盘进行扫描
                                for (i = 0; i &lt; QUEEN; ++i){   //判断列冲突与斜线上的冲突
                                    if (a[i] == col || abs(i - row) == abs(a[i] - col))
                                        return 0;
                                }
                                return 1;
                            }
                             
                            //打印输出N皇后的一组解
                            void print(){
                                int i, j;
                                for (i = 0; i &lt; QUEEN; ++i){
                                    for (j = 0; j &lt; QUEEN; ++j){
                                        if (a[i] != j)      //a[i]为初始值
                                            printf("%c ", '.');
                                        else                //a[i]表示在第i行的第a[i]列可以放置皇后
                                            printf("%c ", '#');
                                    }
                                    printf("\n");
                                }
                                for (i = 0; i &lt; QUEEN; ++i)
                                    printf("%d ", a[i]);
                                printf("\n");
                                printf("--------------------------------\n");
                            }
                             
                            void queen()      //N皇后程序
                            {
                                int n = 0;
                                int i = 0, j = 0;
                                while (i &lt; QUEEN)
                                {
                                    while (j &lt; QUEEN)        //对i行的每一列进行探测，看是否可以放置皇后
                                    {
                                        if(valid(i, j))      //该位置可以放置皇后
                                        {
                                            a[i] = j;        //第i行放置皇后
                                            j = 0;           //第i行放置皇后以后，需要继续探测下一行的皇后位置，
                                                             //所以此处将j清零，从下一行的第0列开始逐列探测
                                            break;
                                        }
                                        else
                                        {
                                            ++j;             //继续探测下一列
                                        }
                                    }
                                    if(a[i] == INITIAL)         //第i行没有找到可以放置皇后的位置
                                    {
                                        if (i == 0)             //回溯到第一行，仍然无法找到可以放置皇后的位置，
                                                                //则说明已经找到所有的解，程序终止
                                            break;
                                        else                    //没有找到可以放置皇后的列，此时就应该回溯
                                        {
                                            --i;
                                            j = a[i] + 1;        //把上一行皇后的位置往后移一列
                                            a[i] = INITIAL;      //把上一行皇后的位置清除，重新探测
                                            continue;
                                        }
                                    }
                                    if (i == QUEEN - 1)          //最后一行找到了一个皇后位置，
                                                                 //说明找到一个结果，打印出来
                                    {
                                        printf("answer %d : \n", ++n);
                                        print();
                                        //不能在此处结束程序，因为我们要找的是N皇后问题的所有解，
                                        //此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。
                                        j = a[i] + 1;             //从最后一行放置皇后列数的下一列继续探测
                                        a[i] = INITIAL;           //清除最后一行的皇后位置
                                        continue;
                                    }
                                    ++i;              //继续探测下一行的皇后位置
                                }
                            }
                             
                            int main(void)
                            {
                                init();
                                queen();
                                system("pause");
                                return 0;
                            }
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            count = 0    #统计解决方案的个数
                            q = [0]*20   #记录各个皇后的放置位置，最多放置 20 个皇后
                            #输出 N 皇后问题的解决方案
                            def display(n):
                                global count
                                count = count + 1
                                print("输出第%d个解：" % (count))
                                for i in range(1 , n + 1):
                                    for j in range(1 , n + 1):
                                        if q[i] != j:
                                            print("x",end=" ");
                                        else:
                                            print("Q",end=" ");
                                    print()
                                print()
                            #检验第k行的第j列是否可以摆放皇后
                            def isSafe(k , j):
                                for i in range(1 , k):
                                    #如果有其它皇后位置同一列上，或者位于该位置的斜线位置上，则该位置无法使用
                                    if q[i] == j or abs(i - k) == abs(q[i] - j):
                                        return False
                                return True
                            #放置皇后到棋盘上
                            def n_queens(k , n):
                                if k > n:      #递归的出口
                                    display(n)
                                else:
                                    for j in range(1 , n + 1): #试探第k行的每一列，找到符合要求的列
                                        if isSafe(k , j):
                                            q[k] = j
                                            n_queens(k + 1 , n); #在确认第 k 行皇后位置的前提下，继续测试下一行皇后的位置
                            print("请输入皇后个数：")
                            n = int(input());
                            n_queens(1,n)
                            print("共有 %d 种不同的排列" % (count))

                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        package 回溯;

                        import java.util.Scanner;

                        public class N皇后_布尔数组 {
	                        int  ways;
	                        /*cols数组标记某一列有没有放过皇后
	                        * leftTop为自左上角到右下角的斜线  n行有2*n-1条
	                        * rightTop为自右上角到左下角的斜线  n行有2*n-1条
	                        * 
	                        */
	                        boolean[]cols;
	                        boolean[]leftTop;
	                        boolean[]rightTop;
	                        void placeQueens(int n) {
		                        if(n&lt;1) return;
		                        cols=new boolean[n];
		                        leftTop=new boolean[n*2];
		                        rightTop=new boolean[n*2];
		                        place(0);
		                        System.out.println(ways);
	                        }
	                        void place(int row) {
		                        if(row==cols.length) {
			                        ways++;
			                        return;
		                        }
		                        for(int col=0;col&lt;cols.length;col++) {
			                        //可行性剪枝
			                        if(cols[col])continue;
			
			                        int ltIndex=row-col+cols.length-1;
			                        if(leftTop[ltIndex])continue;
			
			                        int rtIndex=row+col;			
			                        if(rightTop[rtIndex])continue;
			                        //标记
			                        cols[col]=leftTop[ltIndex]=rightTop[rtIndex]=true;
			                        place(row+1);
			                        //回溯
			                        cols[col]=leftTop[ltIndex]=rightTop[rtIndex]=false;
		                        }
	                        }
	                        public static void main(String[] args) {
		                        Scanner reader=new Scanner(System.in);
		                        new N皇后_布尔数组().placeQueens(4);
		
	
	                        }

                        }


                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
